package com.practice.string;

public class KMP {
	public int indexOf(String string, String pattern) {
		int[] pi = computePrefix(pattern);
		int N = string.length();
		int M = pattern.length();
		
		int j = -1;
		for (int i=0; i<N; i++) {
			while (j >= 0 && pattern.charAt(j+1) != string.charAt(i)) {
				j = pi[j];
			}
			if (pattern.charAt(j+1) == string.charAt(i)) {
				j++;
				if (j == M-1) return i-M+1;
			}
		}
		
		return -1;
	}
	
	public int[] computePrefix(String pattern) {
		int[] pi = new int[pattern.length()];
		int j = -1;
		pi[0] = -1;
		for (int i=1; i<pattern.length(); i++) {
			while (j >= 0 && pattern.charAt(j+1) != pattern.charAt(i)) {
				j = pi[j];
			}
			if (pattern.charAt(j+1) == pattern.charAt(i)) {
				j++;
			}
			pi[i] = j;
		}
		return pi;
	}
}
